স্ট্যাক ও কিউ এর ব্যবহার: ব্যালেন্সড প্যারেনথেসিস, ইনফিক্স থেকে পোস্টফিক্স কনভার্সন

স্ট্যাক ও কিউ এর ব্যবহার

স্ট্যাক এবং কিউ হল দুইটি মৌলিক ডেটা স্ট্রাকচার যা বিভিন্ন কাজের জন্য ব্যবহৃত হয়। এই দুটি ডেটা স্ট্রাকচারগুলি বিশেষ করে সমস্যাগুলির সমাধানে কার্যকরী। নিচে স্ট্যাক এবং কিউ এর দুটি গুরুত্বপূর্ণ ব্যবহার নিয়ে আলোচনা করা হলো: ব্যালেন্সড প্যারেনথেসিস এবং ইনফিক্স থেকে পোস্টফিক্স কনভার্সন।

১. ব্যালেন্সড প্যারেনথেসিস (Balanced Parentheses)

ব্যালেন্সড প্যারেনথেসিস সমস্যা হল চিহ্নগুলির একটি সিকোয়েন্স যা সঠিকভাবে বন্ধ হয় কিনা তা যাচাই করার প্রক্রিয়া। উদাহরণস্বরূপ, "(())" একটি ব্যালেন্সড প্যারেনথেসিস, কিন্তু "(()" একটি ব্যালেন্সড নয়।

স্ট্যাক ব্যবহার করে ব্যালেন্সড প্যারেনথেসিস যাচাই:

def is_balanced(expression):
    stack = []
    opening = {'(': ')', '{': '}', '[': ']'}
    
    for char in expression:
        if char in opening:
            stack.append(char)
        elif char in opening.values():
            if not stack or opening[stack.pop()] != char:
                return False
    return not stack

# পরীক্ষা করা
expression1 = "((()))"
expression2 = "(()"
print(is_balanced(expression1))  # Output: True
print(is_balanced(expression2))  # Output: False

২. ইনফিক্স থেকে পোস্টফিক্স কনভার্সন (Infix to Postfix Conversion)

ইনফিক্স পদ্ধতিতে অপারেটরগুলি অপার্যান্ডগুলির মধ্যে থাকে (যেমন A + B), কিন্তু পোস্টফিক্স পদ্ধতিতে অপারেটরগুলি তাদের অপার্যান্ডগুলির পরে থাকে (যেমন A B +)। স্ট্যাক ব্যবহার করে ইনফিক্সকে পোস্টফিক্সে রূপান্তর করা হয়।

ইনফিক্স থেকে পোস্টফিক্স রূপান্তরের অ্যালগরিদম:

1. একটি স্ট্যাক তৈরি করুন।
2. ইনফিক্স অভিব্যক্তির প্রতিটি চিহ্ন পরীক্ষা করুন:
   • যদি এটি একটি অপার্যান্ড (যেমন সংখ্যা বা ভেরিয়েবল) হয়, তবে এটি আউটপুটে যুক্ত করুন।
   • যদি এটি একটি ওপেনিং প্যারেন্টিসিস হয়, তবে স্ট্যাকে যুক্ত করুন।
   • যদি এটি একটি ক্লোজিং প্যারেন্টিসিস হয়, তবে স্ট্যাক থেকে ওপেনিং প্যারেন্টিসিস পর্যন্ত অপারেটরগুলি বের করুন এবং আউটপুটে যুক্ত করুন।
   • যদি এটি একটি অপারেটর হয়, তবে প্রিওরিটি অনুযায়ী স্ট্যাক থেকে অপারেটরগুলি বের করুন এবং তাদের আউটপুটে যুক্ত করুন, তারপর বর্তমান অপারেটরটি স্ট্যাকে যুক্ত করুন।
3. সমস্ত ইনপুট প্রক্রিয়া হওয়ার পরে, স্ট্যাক থেকে সমস্ত অপারেটর বের করে আউটপুটে যুক্ত করুন।

ইনফিক্স থেকে পোস্টফিক্স রূপান্তর কোড (Python):

def precedence(op):
    if op == '+' or op == '-':
        return 1
    if op == '*' or op == '/':
        return 2
    return 0

def infix_to_postfix(expression):
    stack = []
    output = []
    
    for char in expression:
        if char.isalnum():  # Operand
            output.append(char)
        elif char == '(':
            stack.append(char)
        elif char == ')':
            while stack and stack[-1] != '(':
                output.append(stack.pop())
            stack.pop()  # Remove '(' from stack
        else:  # Operator
            while (stack and precedence(stack[-1]) >= precedence(char)):
                output.append(stack.pop())
            stack.append(char)

    while stack:
        output.append(stack.pop())
    
    return ''.join(output)

# পরীক্ষা করা
infix_expression = "A+B*(C^D-E)"
postfix_expression = infix_to_postfix(infix_expression)
print(f"Infix: {infix_expression} -> Postfix: {postfix_expression}")

উপসংহার

স্ট্যাক এবং কিউ হল দুটি গুরুত্বপূর্ণ ডেটা স্ট্রাকচার যা বিভিন্ন সমস্যার সমাধানে ব্যবহৃত হয়। ব্যালেন্সড প্যারেনথেসিস যাচাই এবং ইনফিক্স থেকে পোস্টফিক্স রূপান্তর করা দুইটি উদাহরণ। এই প্রযুক্তিগুলি প্রোগ্রামিংয়ে বিভিন্ন সমস্যার সমাধানে কার্যকর এবং দক্ষতা বৃদ্ধি করতে সাহায্য করে।